// [dfs递归]猴子爬山分级递推
// 一个顽猴在一座有40级台阶的山上爬山跳跃，猴子上山一步可跳1级或跳3级，
// 试求顽猴上山的40级台阶有多少种不同的跳法；
// 1.递推设计：
// 这一问题实际上是一个整数有序可重复拆分问题；
// 试设置数组应用递推求解，设上k级台阶的不同跳法为f（k）种；
// 则：
// f(1) = 1;即1=1
// f(2) = 1;即2=1+1
// f(3) = 2;即3=1+1+1;3
// f(4) = 3;即4=1+1+1+1;3+1;1+3(f(4)=f(3)+f(1))
#include <stdio.h>
#include <stdlib.h>
int f(int n) {
  int zh;
  if (n == 1 || n == 2) zh = 1;
  if (n == 3) zh = 2;
  if (n > 3) zh = f(n - 1) + f(n - 3);
  return zh;
}

int main() {
  f(8);
  return 0;
}